package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202409;

import java.util.ArrayDeque;
import java.util.Deque;

public class leetcode20240913 {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int ans=0,left=0;
        long sum=0;
        Deque<Integer> dq=new ArrayDeque<>();
        for(int right=0;right<runningCosts.length;right++){
            // 1、入队列
            while(!dq.isEmpty() && chargeTimes[right]>=chargeTimes[dq.peekLast()]){
                dq.pollLast();
            }
            dq.addLast(right);
            sum+=runningCosts[right];

            // 2、出队列
            while(!dq.isEmpty() && chargeTimes[dq.peekFirst()]+(right-left+1)*sum>budget){
                if(dq.peekFirst()==left){
                    dq.pollFirst();
                }
                sum-=runningCosts[left++];
            }
            ans=Math.max(ans,right-left+1);
        }
        return ans;
    }
}
